package blatt8;

import java.io.FileNotFoundException;
import java.io.RandomAccessFile;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

public class Editierdistanz  {

	private static int[][] matrix;
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		if (args.length > 0) {
			
			if (args.length == 1) {
				
				List<String> zeilenA, zeilenB;
				zeilenA = zeilenB = getZeilen(args[0]); // Einlesen

				for(String zeileA : zeilenA) {
					for(String zeileB : zeilenB) {
						if (!zeileA.equals(zeileB))
							System.out.format("\nDie LV-Distanz zwischen '%s' und '%s' beträgt %s", zeileA, zeileB, berechneDistanz(zeileA, zeileB));
					}
				}
			} else {
								
				System.out.format("\nDie LV-Distanz zwischen '%s' und '%s' beträgt %s", args[0], args[1], berechneDistanz(args[0], args[1]));
				System.out.println(backtrace(matrix.length-1, matrix[0].length-1));
			}
		}
	}
	
	@SuppressWarnings({ "finally", "resource" })
	public static List<String> getZeilen(String dateipfad) {
		
		RandomAccessFile file;
		String zeile;
		List<String> zeilen = new ArrayList<String>();
		
		try {
			
			file = new RandomAccessFile(dateipfad, "r");
			while (null != (zeile = file.readLine())) {
				zeilen.add(zeile.trim());
			}
			
		} catch (ClassCastException e) {
			System.out.println("No Comparable Implementation Fehler.");
		} catch (SecurityException e) {
			System.out.println("Kein Zugriffsrecht auf übergebene Datei.");
		} catch (FileNotFoundException e) {
			System.out.println("Die Übergebene Datei konnte nicht gefunden werden. \n" + e.getMessage());
		} catch (NumberFormatException e) {
			System.out.println("Eine ungültige Zahl wurde übergeben, oder stand in der übergebenen Datei.");
		} catch (IllegalArgumentException e) {
			System.out.println("Falsche Argumente: " + e.getMessage());
		} catch (IndexOutOfBoundsException e) {
			System.out.println("Da lief ein Index raus: " + e.getMessage());
		} catch (NoSuchElementException e) {
			System.out.println("Die einzulesene Datei ist fehlerhaft. Eventuell enthält eine Zeile nicht genau zwei Token.");
		} catch (ArrayStoreException e) {
			System.out.println("Interner Verarbeitungsfehler: Eine Element konnte nicht ins andere Array kopiert werden, da unterschiedliche Typen verwendet wurden. " + e.getMessage());
		} catch (Exception e) {
			System.out.println("Fehler: " + e.getMessage());
		} finally {
			return zeilen;
		}
	}

	public static int berechneDistanz(String a, String b) {
		
		
		int n = a.length(), 
			m = b.length(), 
			p[] = new int[n + 1], 	// Kosten des vorherigen Arrays, horizontal
			d[] = new int[n + 1], 	// Kosten des Arrays, horizontal
			_d[], 					// Temporäres Swap-Array für p und d
			i = 0, 
			j = 0,
			cost;
		char charInT;
		
		matrix = new int[m+1][n+1];

		if (n == 0 || m == 0) {
			// Falls eines der beiden Argument null ist, wird die 
			// Länge des anderen Strings zurückgegeben, 
			// da jeweils n, bzw. m einsetzungen gebraucht werden
			return Math.max(m, n);
		}

		// Erste Zeile mit Positionswerten füllen
		for (i = 0; i <= n; i++) {
			p[i] = i; 	// {0,1,..,n}
		}

		matrix[0] = p;
		
		for (j = 1; j <= m; j++) {
			// Für jedes Zeichen in m ("Zeile" in der Vergleichsmatrix n[m])
			charInT = b.charAt(j - 1);
			d[0] = j;
			
			// Mit 
			for (i = 1; i <= n; i++) {
				
				// Aktuelles Zeichen in s mit Zeichen der äußeren Schleife aus t vergleichen
				cost = (a.charAt(i - 1) == charInT) ? 0 : 1;
				// Kleinste Kosten aus der (linken+1), (oberen+1) und (oberen linken (Diagonal) Zelle + aktuelle Kosten)
				d[i] = dap.util.min(d[i - 1] + 1, p[i] + 1, p[i - 1] + cost);
			}
			
			matrix[j] = d;
			
			// Aktuelle Levenstheinsche' Distanz im Vergleich zur vorherigen Reihe zwischenspeichern
			_d = p;
			p = d;
			d = _d;
		}
		
		// Rückgabe der minimalen Levenstheinschen' Distanz
		return p[n];
	}
	
	public static String backtrace(int i, int j) {
		if (i>0 && matrix[i-1][j] + 1 == matrix[i][j]) 			return backtrace(i-1, j) + " Del ";
		if (j>0 && matrix[i][j-1] + 1 == matrix[i][j]) 			return backtrace(i, j-1) + " Ins ";
		if (i>0 && j>0 && matrix[i-1][ j-1] + 1 == matrix[i][j])return backtrace(i-1, j-1) + " Rep ";
		if (i>0 && j>0 && matrix[i-1][j-1]  == matrix[i][j]) 	return backtrace(i-1,j-1) + " Eq ";
		return "";
	}

}
